#include <gtest/gtest.h>
#include "common.h"
#include <unordered_set>

using namespace ::std;

class Solution {
public:
    bool hasCycle(ListNode *head);
};

bool Solution::hasCycle(ListNode *head) {
    // set<ListNode*> s;
    unordered_set<ListNode*> s; // 在这个场景中，性能并没有提升
    while(head != nullptr) {
        if(s.find(head) == s.end()) s.insert(head);
        else return true;
        head = head->next;
    }
    return false;
}

class HasCycleCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(HasCycleCheck, testHasCycle_1) {
    int pos = 1;
    vector<int> value = {3,2,0,-4};
    ListNode* head = makeCycleLinkedList(value, pos);
    EXPECT_TRUE(true == solution.hasCycle(head));
}

TEST_F(HasCycleCheck, testHasCycle_2) {
    int pos = 0;
    vector<int> value = {1,2};
    ListNode* head = makeCycleLinkedList(value, pos);
    EXPECT_TRUE(true == solution.hasCycle(head));
}

TEST_F(HasCycleCheck, testHasCycle_3) {
    int pos = -1;
    vector<int> value = {1};
    ListNode* head = makeCycleLinkedList(value, pos);
    EXPECT_TRUE(false == solution.hasCycle(head));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
